The invention relates generally to data storage and/or communication systems. More particularly, the invention relates to the iterative soft and hard decoding of linear codes defined by the parity check matrices composed from submatrices with a cyclic property (circulants).
Recently, various types of turbo codes have been proposed for communication channels and storage systems. Combined with a BCJR (Bahl, Cocke, Jelinek and Raviv) algorithm or a Soft-Output Viterbi Algorithm (SOVA) those codes provide flexible tradeoffs in complexity and Bit Error Rate (BER). But due to the high latency of the decoding process, turbo codes are inappropriate for extremely high speed communication and high-density magnetic recording applications.
Similar BER characteristics at the lower level of complexity can be also achieved by the use of the Gallager Low Density Parity Check (LDPC) codes defined by a parity check matrix with some small fixed number of ones in each column. Originally, the LDPC codes have been constructed by random choice of the parity check matrix, but such codes require very complex encoders and decoders in general. Despite tremendous progress in achieving BER characteristics using LDPC codes, the problems of implementation complexity were left aside until the current time. A significant insight into the nature of iterative decoding has been gained due to interpretation of the decoding algorithms in terms of belief propagation in graphical models, but these graphical models of message passing are used mainly for the illustrative purposes, and the complexity factors still dominate system architecture and design considerations, especially in extremely high speed applications such as magnetic recording. The high complexity of the existing schemes is a direct consequence of the fact that parity check matrices of the random LDPC codes do not have a regular structure, and therefore large amounts of memory and logic gates are required to build corresponding encoders and decoders.
The results of several studies of LDPC based communication and storage systems have been recently reported and several schemes based on random regular and irregular LDPC codes have been described. The irregular LDPCs have parity check matrices with multiple column weights and linearly dependant rows (deficient rank parity check matrix). These codes enable faster encoding since the dimension of the systematic form of the parity check matrix used to calculate parity bits turns out to be much smaller than the number of parity check equations used in decoding. However, the parity check matrix of an irregular code is still similar to the random structure of a Gallager LDPC. Another approach is the algebraic construction of LDPC codes using finite geometries. The finite geometry LDPC codes are quasi-cyclic and their encoders can be implemented using linear shift registers with feedback connections defined by the generator polynomial of the code. The resulting codes have been demonstrated to have excellent performance in AWGN, although their rates are still low for high data rate applications, and decoder complexities are somewhat high.
A class of structured high rate LDPC codes with orthogonal parities has been constructed from Kirkman triple systems. Both finite geometries and Kirkman systems are special classes of the Balanced Incomplete Block Designs (BIBD). Although many different types of the BIBD are described in the mathematical literature, not many of them give LDPC codes with high rates and sufficiently large minimum Hamming distances.
Therefore, the complexity issues remain to be the dominant factor that prevent the wide use of the LDPC based architectures, especially in extremely high speed applications such as magnetic recording. The high complexity of the existing schemes is a direct consequence of the fact that parity check matrices of the random LDPC codes do not have a regular structure, and therefore large amounts of memory and logic gates are required to build corresponding encoders and decoders. A proposed method of overcoming the problems of implementation complexity would be a significant improvement in the art.
The present invention provides a novel method and apparatus for decoding digital information transmitted through the communication channel or recorded on a recording medium. In some embodiments of the invention, the method and apparatus are applied in the systems where data is encoded using structured LDPC codes with parity check matrices composed from circulants (a matrix is called a circulant if all its columns or rows are cyclic shifts of each other). A class of such codes is constructed from integer lattices, and described later. A more complete understanding of the present invention, as well as other features and advantages of the present invention, may be obtained with reference to the following detailed description and accompanying drawings.